package LearnDataStructure.c_树结构.例题;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-13 13:01
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */

/*
求两个节点的最近公共祖先节点
规定1：如果两个节点是父子关系，那么父节点就是最近公共祖先节点
贵定2：如果两个节点是相同节点，那么它们互为最近公共祖先节点
 */
public class i_求LCA可利用parent {
    public static void main(String[] args) {
        i_求LCA可利用parent test = new i_求LCA可利用parent();

        b_MyBinaryTreebyLinked<Integer,Integer> binaryTree2 = new b_MyBinaryTreebyLinked<>();

        binaryTree2.insert(6,6);
        BSTNode<Integer, Integer> node1 = binaryTree2.insert(7, 7);
        binaryTree2.insert(4,4);
        binaryTree2.insert(5,5);
        BSTNode<Integer, Integer> node = binaryTree2.insert(8, 8);
        binaryTree2.insert(2,2);

        System.out.println(binaryTree2);
        System.out.println(test.getLCA2(binaryTree2.getRoot(), 7,8));
    }

    /**
     * 递归，使用额外数据结构,使用parent
     * @param node
     * @param p
     * @param q
     * @return
     */
    public Integer getLCA2(BSTNode<Integer,Integer> node, Integer p, Integer q) {
        BSTNode<Integer, Integer> headP = dfsFindTarget(node, p);
        BSTNode<Integer, Integer> headQ = dfsFindTarget(node, q);

        BSTNode<Integer, Integer> copyP = headP;
        BSTNode<Integer, Integer> copyQ = headQ;
        int countp = 0;
        int countq = 0;
        while (copyP != null) {
            countp++;
            copyP = copyP.parent;
        }
        while (copyQ != null) {
            countq++;
            copyQ = copyQ.parent;
        }
        int num = 0;
        if (countp > countq) {
            num = countp - countq;
            copyP = headP;
            copyQ = headQ;
            for (int i = 0; i < num; i++) {
                headP = headP.parent;
            }
        } else {
            num = countq - countp;
            copyP = headP;
            copyQ = headQ;
            for (int i = 0; i < num; i++) {
                copyQ = copyQ.parent;
            }
        }
        while (!copyP.key.equals(copyQ.key)) {//只要p,q是存在树里的，这个链表的遍历就不会空指针异常；因为root肯定是p,q的公共祖先
            copyP = copyP.parent;
            copyQ = copyQ.parent;
        }
        return copyP.key;
    }

    public BSTNode<Integer,Integer> dfsFindTarget(BSTNode<Integer,Integer> node, Integer target) {
        if (node == null) {
            return null;
        }

        if (node.value.equals(target)) {
            return node;
        }

        BSTNode<Integer, Integer> resLeft = dfsFindTarget(node.left, target);
        BSTNode<Integer, Integer> resRight = dfsFindTarget(node.right, target);

        if (resLeft == null && resRight == null) {
            return null;
        }

        return resLeft != null ? resLeft : resRight;
    }
}
